Although relational data stores can be used to index and serve geospatial data using an inverted index, these systems are often not optimized for location-based search queries. Because of this, the execution of location-based search queries against the relational data stores often results in a long latency period before search results are returned. For example, in existing systems there may be a 200 to 400 millisecond lag between when a location-based query is received and when results are returned.